#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;


//图的度 
/*
 int n,m;
 vector<int> g[N];
 int main(){
 cin>>n>>m;
 for(int i=1;i<=m;i++){
 int x,y;
 cin>>x>>y;
 g[x].push_back(y);
 g[y].push_back(x);
 }
 for(int i=1;i<=n;i++){
 cout<<g[i].size()<<" ";
 }
 return 0;
 }
*/


//无向图 
/*
#include<bits/stdc++.h>
 using namespace std;
 const int N=5e2+10;
 int g[N][N];
 int n,m;
 int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        if(a==b){
            printf("No\n");
            return 0;
        }
        if(g[a][b]==1) {
            printf("No\n");
            return 0;
        }
        g[a][b]=g[b][a]=1;
    }
    printf("Yes");
 }

*/


//暴力 
/*
int n;
int a[N];
ll ans;
int main()
{
  scanf("%d",&n);
  for(int i = 1; i <= n ; ++i){
    scanf("%d",&a[i]);
  }
  for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= n; ++j){
        if(j == i)	continue;

        for(int l = 1; l <= n; ++l){

            if(j == l || i == l)	continue;
            for(int k = 1; k <= n; ++k){
                if(j == k || i == k || l == k)  continue;

                if((a[k] % a[i]==0) && (a[l] % a[j]==0)){
                    ans++;
                }
            }
        }
    }
  }
  cout<<ans;


  return 0;
}
*/

//训练士兵
/*
int n;
ll s;

int max_ci;
ll all_count = (ll)1e18;
ll p1[N];
ll c1p1[N];
struct node {
    int c;
    int p;
}a[N];

bool tmp(node& a, node& b) {
    return a.c < b.c;
}


int main()
{
    cin >> n >> s;
    // 请在此输入您的代码
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].p;
        cin >> a[i].c;       
    }
    sort(a + 1, a + n + 1, tmp);

    for (int i = 1; i <= n; ++i) {
        p1[i] = p1[i - 1] + a[i].p;
        c1p1[i] = c1p1[i - 1] + 1ll * a[i].p * a[i].c;
    }
    ll sum = 0;
    for (int i = 0; i <= n; ++i) {
        sum = 1ll*s * a[i].c + c1p1[n] - c1p1[i] - (p1[n] - p1[i]) * a[i].c *1ll;
        all_count = min(all_count, sum);
    }
    cout << all_count;

    
    return 0;
}
*/

/*
struct node {
    int p, c;
} a[100005];

int main() {
    int n;
    long long S;
    cin >> n >> S;
    for (int i = 1; i <= n; i++)
        cin >> a[i].p >> a[i].c;
    sort(a + 1, a + 1 + n, [](node n1, node n2) {
        return n1.c < n2.c;
        });

    long long sum = 0;
    int loc = 0;
    for (int i = n; i >= 1; i--) {
        sum += a[i].p;
        if (sum >= S) {
            loc = i;
            break;
        }
    }

    long long ans = a[loc].c * S;
    for (int i = loc + 1; i <= n; i++)
        ans += (long long)(a[i].c - a[loc].c) * a[i].p;
    cout << ans << '\n';

    return 0;
}
*/
    